import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here

        //动态规划解法
        //dp[i][j]表示str1以第i位置结尾的字符串和str2以第j位置结尾的字符串的最长公共子串的长度

        int[][] dp=new int[str1.length()+1][str2.length()+1];
        int max=0;//记录最长公共子串的长度
        int pos=0;//记录遍历到的最长的子串的最后一个字符下标

        for(int i=1;i<str1.length()+1;i++){

            for(int j=1;j<str2.length()+1;j++){

                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j]=1+dp[i-1][j-1];//因为有i-1,j-1,所以开始时另i=1,j=1
                    //当前公共子串的最长=之前保存的max+1
                }else{
                    dp[i][j]=0;//如果不字符不相等，置为0
                }

                if(dp[i][j]>max){
                    max=dp[i][j];
                    pos=i-1;//记得保存当前最长公共子串的下标

                }
            }
        }
        return str1.substring(pos-max+1,pos+1);
    }
}